<!DOCTYPE html>
<html class="client-nojs vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-0 vector-toc-not-available vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-0 skin-theme-clientpref-day vector-sticky-header-enabled" lang="de" dir="ltr"><head>
<meta charset="UTF-8">
<title>Bitmap-Index</title>
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<link rel="icon" type="image/png" href="./_res_/favicon.png">
<link rel="canonical" href="https://de.wikipedia.org/wiki/Bitmap-Index"> <link href="./_mw_/ext.wikimediamessages.styles.css" rel="stylesheet" type="text/css">
<link href="./_mw_/skins.vector.icons.css" rel="stylesheet" type="text/css">
<link href="./_mw_/skins.vector.search.codex.styles.css" rel="stylesheet" type="text/css">
<link href="./_mw_/skins.vector.styles.css" rel="stylesheet" type="text/css">
<meta name="ResourceLoaderDynamicStyles" content="">
<link href="./_mw_/ext.gadget.citeRef.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.gadget.defaultPlainlinks.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.gadget.dewikiCommonHide.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.gadget.dewikiCommonLayout.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.gadget.dewikiCommonStyle.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.gadget.dewikiDarkmode.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.gadget.dewikiResponsive.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.gadget.specialSearch.css" rel="stylesheet" type="text/css">
<link rel="stylesheet" type="text/css" href="./_mw_/site.styles.css">
<link rel="stylesheet" type="text/css" href="./_mw_/noscript.css">
<link rel="stylesheet" type="text/css" href="./_res_/footer.css">
<link rel="stylesheet" type="text/css" href="./_res_/vector-2022.css">
</head>
<body class="skin--responsive skin-vector skin-vector-search-vue mediawiki ltr sitedir-ltr mw-hide-empty-elt ns-0 ns-subject page-Bitmap-Index rootpage-Bitmap-Index skin-vector-2022 action-view">
<div class="mw-page-container">
<div class="mw-page-container-inner">
<div class="mw-content-container">
<main id="content" class="mw-body">
<header class="mw-body-header vector-page-titlebar">
<h1 id="firstHeading" class="firstHeading mw-first-heading"><span class="mw-page-title-main">Bitmap-Index</span></h1>
</header>
<a id="top"></a>
<div id="bodyContent" class="vector-body ve-init-mw-desktopArticleTarget-targetContainer" aria-labelledby="firstHeading" data-mw-ve-target-container="">
<div id="contentSub">
<div id="mw-content-subtitle"></div>
</div>
<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="de" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="de" dir="ltr"><p>Ein <b>Bitmap-Index</b> ist ein <a href="Datenbankindex" title="Datenbankindex">Datenbankindex</a>, der dazu dient, mehrdimensionale <a href="Daten" title="Daten">Daten</a> effizient zu indizieren. Auf Grund seiner Eigenschaften findet der Bitmap-Index vor allem bei <a href="Data-Warehouse" class="mw-redirect" title="Data-Warehouse">Data Warehouses</a> Einsatz.
</p><p>Die Bezeichnung rührt daher, dass der Bitmap-Index ein oder mehrere Attribute in Form eines <a href="Bit" title="Bit">Bitmusters</a> (<i>engl. Bitmap</i>) speichert. Er ist vor allem sinnvoll einsetzbar für die Indizierung von Tabellenspalten mit einer geringen <a href="Kardinalit%C3%A4t_(Datenbanken)" title="Kardinalität (Datenbanken)">Kardinalität</a> (Anzahl der in dieser Spalte vorhandenen unterschiedlichen Werte). Das ist genau der Bereich, in dem ein konventioneller Index, realisiert durch einen <a href="B-Baum" title="B-Baum">B-Baum</a>, keine Steigerung der Zugriffsperformance bringt.
</p>
<div class="mw-heading mw-heading2"><h2 id="Beispiel">Beispiel</h2></div>
<p>Ein einfaches Beispiel: in einen Index einer Personendatenbank werden die Attribute <i>Geschlecht</i> (zwei mögliche Werte, Kardinalität = 2) und <i>Familienstand</i> (Kardinalität = 3) eingetragen. Die Indextabelle könnte so aussehen:
</p>
<table class="wikitable">
<tbody><tr>
<th>Name</th>
<th>männlich</th>
<th>weiblich</th>
<th>ledig</th>
<th>verheiratet</th>
<th>geschieden
</th></tr>
<tr>
<td>Anne</td>
<td>0</td>
<td>1</td>
<td>0</td>
<td>1</td>
<td>0
</td></tr>
<tr>
<td>Emil</td>
<td>1</td>
<td>0</td>
<td>0</td>
<td>0</td>
<td>1
</td></tr>
<tr>
<td>Fritz</td>
<td>1</td>
<td>0</td>
<td>0</td>
<td>1</td>
<td>0
</td></tr>
<tr>
<td>Hans</td>
<td>1</td>
<td>0</td>
<td>0</td>
<td>1</td>
<td>0
</td></tr>
<tr>
<td>Willi</td>
<td>1</td>
<td>0</td>
<td>1</td>
<td>0</td>
<td>0
</td></tr></tbody></table>
<div class="mw-heading mw-heading2"><h2 id="Funktionsweise">Funktionsweise</h2></div>
<p>Wie bei allen Datenbankindizes existiert von jedem dieser Einträge ein Verweis auf einen (externen) Datenbankeintrag.
</p><p>Das Durchsuchen der (vorzugsweise intern gespeicherten) Indextabelle geschieht über einfache binäre Operationen, im Beispiel über <a href="Konjunktion_(Logik)" title="Konjunktion (Logik)">Und-Verknüpfung</a> mit einer Suchmaske. Sucht man in dem Beispiel nach Personen, die männlich und verheiratet sind, so ist die Suchmaske 10 010 (die Verweise der Treffer führen zu Fritz und Hans).
</p><p>Ausnutzung der binären Operationen auf <a href="Prozessor" title="Prozessor">Prozessorebene</a> bietet einen Geschwindigkeitsvorteil bei Vergleichsoperationen. Durch diese Repräsentation wird Rechenaufwand gegen Speicherplatz getauscht.
</p>
<div class="mw-heading mw-heading2"><h2 id="Abbildung_des_Wertebereichs">Abbildung des Wertebereichs</h2></div>
<p>Die Zuordnung von einem Wert eines Wertebereichs zu einem <a href="Bitvektor" class="mw-redirect" title="Bitvektor">Bitvektor</a> geschieht durch die Wahl der Basis des Bitvektors. Wird jedem Wert des Wertebereichs eindeutig ein einziger Bitvektor zugeordnet, so entspricht die Länge des Bitvektors im einfachen Fall genau der Kardinalität des Wertebereichs und ist gleichzeitig Basis des Bitvektors.
Ein Vorteil dieser Darstellung ist die Möglichkeit, einzelne Werte eines Wertebereichs auszulassen, wenn diese nicht in vorliegenden Daten vorkommen.
Weiterhin besteht die Möglichkeit, eine nicht uniforme Basis anzugeben.
</p>
<div class="mw-heading mw-heading2"><h2 id="Literatur">Literatur</h2></div>
<ul><li>Chee-Yong Chan und Yannis Ioannidis: <i>Bitmap Index Design and Evaluation</i>. Proceedings of the 1998 ACM SIGMOD Conference.</li></ul></div><!--htdig_noindex--><div><div class="zim-footer">
Dieser Artikel wurde von <a class="external text" title="Zuletzt bearbeitet am 2015-09-12" href="https://de.wikipedia.org/wiki/?title=Bitmap-Index&oldid=145965856">Wikipedia</a> herausgegeben. Der Text ist unter <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.de">Creative Commons Attribution-Share Alike 4.0</a> verfügbar, sofern nicht anders angegeben. Für die Mediendateien können zusätzliche Bedingungen gelten.
</div>
</div><!--/htdig_noindex--></div>
</div>
</main>
</div>
</div>
</div>
<script src="./_webp_/webpHandler.js"></script>
</body></html>